By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

ALERT ATTENTION: System maintenance will be performed the weekend of Saturday, March 28, 2009. This event will begin at 6:00 am on March 28 and will conclude at approximately 12:00 noon on Sunday March 29 (all times EDT). Some Scitation services may be affected during this period.
Table of Contents
Search This Issue
Volume 23, Issue 1, pp. 1-225

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

Computational Complexity of Sparse Rational Interpolation

Dima Grigoriev, Marek Karpinski, and Michael F. Singer

pp. 1-11

BibTeX  Abstract Full Text:  PDF

Tight Upper and Lower Bounds on the Path Length of Binary Trees

Alfredo De Santis and Giuseppe Persiano

pp. 12-23

BibTeX  Abstract Full Text:  PDF

Unique Binary-Search-Tree Representations and Equality Testing of Sets and Sequences

Rajamani Sundar and Robert E. Tarjan

pp. 24-44

BibTeX  Abstract Full Text:  PDF

A Complexity Index for Satisfiability Problems

E. Boros, Y. Crama, P. L. Hammer, and M. Saks

pp. 45-49

BibTeX  Abstract Full Text:  PDF

The Set Union Problem with Unlimited Backtracking

Alberto Apostolico, Giuseppe F. Italiano, Giorgio Gambosi, and Maurizio Talamo

pp. 50-70

BibTeX  Abstract Full Text:  PDF

The Profile Minimization Problem in Trees

David Kuo and Gerard J. Chang

pp. 71-81

BibTeX  Abstract Full Text:  PDF

Modifications of Competitive Group Testing

D.-Z. Du, G.-L. Xue, S.-Z. Sun, and S.-W. Cheng

pp. 82-96

BibTeX  Abstract Full Text:  PDF

The Complexity of Decision Versus Search

Mihir Bellare and Shafi Goldwasser

pp. 97-119

BibTeX  Abstract Full Text:  PDF

Homeomorphism of $2$-Complexes is Graph Isomorphism Complete

John Shawe-Taylor and Tomaz Pisanski

pp. 120-132

BibTeX  Abstract Full Text:  PDF

On Collision-Free Placements of Simplices and the Closest Pair of Lines in $3$-Space

Marco Pellegrini

pp. 133-153

BibTeX  Abstract Full Text:  PDF

Fat Triangles Determine Linearly Many Holes

Jirí Matousek, János Pach, Micha Sharir, Shmuel Sifrony, and Emo Welzl

pp. 154-169

BibTeX  Abstract Full Text:  PDF

Three-dimensional Statistical Data Security Problems

Robert W. Irving and Mark R. Jerrum

pp. 170-184

BibTeX  Abstract Full Text:  PDF

An NC Algorithm for Scheduling Unit-Time Jobs with Arbitrary Release Times and Deadlines

Greg N. Frederickson and Susan H. Rodger

pp. 185-211

BibTeX  Abstract Full Text:  PDF

Broadcasting and Gossiping in de Bruijn Networks

Jean-Claude Bermond and Pierre Fraigniaud

pp. 212-225

BibTeX  Abstract Full Text:  PDF